`:top

Mittels der `!Substitutionsmethode`! für Rekurrenzen lässt sich eine `F33f`_`[untere Schranke`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Landau-Symbole]`_`f bzw. obere Schranke des (Rechen-)Aufwandes einer `F33f`_`[Rekursion`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Rekursion]`_`f bestimmen.

>>Contents

• `F0af`_`[Beschreiben der Methode`#beschreiben-der-methode]`_`f

• `F0af`_`[Beispiel`#beispiel]`_`f

-─

>>Beschreiben der Methode

Gegeben sei eine Rekursion T(n) der Form T(n) = a⋅T(n/b) + f(n). Um eine obere Schranke zu ermitteln, schätzt man diese zuerst mittels `F33f`_`[Ο-Kalkül`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Landau-Symbole]`_`f ab. Unter Abschätzen versteht man „geschicktes Raten“. Anschließend wird die Vermutung mit Hilfe von Substitution bewiesen bzw. widerlegt. Analog ist das Vorgehen zur Bestimmung der unteren Schranke.

1. Vermutung(1): T(n) ≤ c⋅g(n), mit c > 0 bzw. T(n) ∈ Ο(g(n)) (nach Definition des Ο-Kalküls)

2. Annahme(2): Tsub(n/b) ≤ c⋅g(n/b)

3. Substitution durch Einsetzen der Annahme in die Rekurrenz: T(n) ≤ a⋅Tsub(n/b) + f(n) bzw. T(n) ≤ a⋅(c⋅g(n/b)) + f(n)

4. Genaues(3) Umformens zu: T(n) ≤ c⋅g(n) → Falls dies nicht möglich ist, so war entweder die Vermutung oder die Annahme(2) falsch.

5. Beweis von T(n) ≤ c⋅g(n) durch Induktion ⇒ T(n) ∈ Ο(g(n))

>>Beispiel

• `!Beispiel (1)`!: T ( n ) = 2 T ( ⌊ n 4 ⌋ ) + 8 T ( ⌊ n 16 ⌋ ) + n {\\displaystyle T(n)=2T\\left(\\left\\lfloor {\\frac {n}{4}}\\right\\rfloor \\right)+8T\\left(\\left\\lfloor {\\frac {n}{16}}\\right\\rfloor \\right)+n}

1. Vermutung: T ( n ) ∈ ∈ O ( n ln ⁡ ⁡ ( n ) ) ⟹ ⟹ T ( n ) ≤ ≤ c ⋅ ⋅ n ln ⁡ ⁡ ( n ) {\\displaystyle T(n)\\in O(n\\ln(n))\\Longrightarrow T(n)\\leq c\\cdot n\\ln(n)}

2. Annahme: T s u b 1 ( n 4 ) ≤ ≤ c ⋅ ⋅ ( n 4 ) ln ⁡ ⁡ ( n 4 ) {\\displaystyle T_{sub1}\\left({\\frac {n}{4}}\\right)\\leq c\\cdot \\left({\\frac {n}{4}}\\right)\\ln \\left({\\frac {n}{4}}\\right)} und T s u b 2 ( n 16 ) ≤ ≤ c ⋅ ⋅ ( n 16 ) ln ⁡ ⁡ ( n 16 ) {\\displaystyle T_{sub2}\\left({\\frac {n}{16}}\\right)\\leq c\\cdot \\left({\\frac {n}{16}}\\right)\\ln \\left({\\frac {n}{16}}\\right)}

3. Substitution: T ( n ) ≤ ≤ 2 ⋅ ⋅ T s u b 1 ( n 4 ) + 8 T s u b 2 ( n 16 ) + n {\\displaystyle T(n)\\leq 2\\cdot T_{sub1}\\left({\\frac {n}{4}}\\right)+8T_{sub2}\\left({\\frac {n}{16}}\\right)+n}

4. Umformen: = 2 ( c ⋅ ⋅ ( n 4 ) ln ⁡ ⁡ ( n 4 ) ) + 8 ( c ⋅ ⋅ ( n 16 ) ln ⁡ ⁡ ( n 16 ) ) + n {\\displaystyle =2\\left(c\\cdot \\left({\\frac {n}{4}}\\right)\\ln \\left({\\frac {n}{4}}\\right)\\right)+8\\left(c\\cdot \\left({\\frac {n}{16}}\\right)\\ln \\left({\\frac {n}{16}}\\right)\\right)+n} = c ⋅ ⋅ n 2 ( ln ⁡ ⁡ ( n ) − − ln ⁡ ⁡ ( 4 ) ) + c ⋅ ⋅ n 2 ( ln ⁡ ⁡ ( n ) − − ln ⁡ ⁡ ( 16 ) ) + n {\\displaystyle =c\\cdot {\\frac {n}{2}}\\left(\\ln(n)-\\ln(4)\\right)+c\\cdot {\\frac {n}{2}}\\left(\\ln(n)-\\ln(16)\\right)+n} = c ⋅ ⋅ n 2 ( 2 ln ⁡ ⁡ ( n ) − − ln ⁡ ⁡ ( 4 ) − − ln ⁡ ⁡ ( 16 ) ) + n {\\displaystyle =c\\cdot {\\frac {n}{2}}\\left(2\\ln(n)-\\ln(4)-\\ln(16)\\right)+n} = c ⋅ ⋅ n ln ⁡ ⁡ ( n ) − − c ⋅ ⋅ n 2 ( ln ⁡ ⁡ ( 4 ) + ln ⁡ ⁡ ( 16 ) ) + n {\\displaystyle =c\\cdot n\\ln(n)-c\\cdot {\\frac {n}{2}}\\left(\\ln(4)+\\ln(16)\\right)+n} ≤ ≤ c ⋅ ⋅ n ln ⁡ ⁡ ( n ) {\\displaystyle \\leq c\\cdot n\\ln(n)} mit c ≥ ≥ 2 ln ⁡ ⁡ ( 4 ) + ln ⁡ ⁡ ( 16 ) = 2 ln ⁡ ⁡ ( 64 ) {\\displaystyle c\\geq {\\frac {2}{\\ln(4)+\\ln(16)}}={\\frac {2}{\\ln(64)}}}

5. Induktion: I.A.: n = 2 : T ( 2 ) = 2 ≤ ≤ c ⋅ ⋅ 2 ln ⁡ ⁡ ( 2 ) = {\\displaystyle n=2:\\quad T(2)=2\\leq c\\cdot 2\\ln(2)=} mit c ≥ ≥ ln − − 1 ⁡ ⁡ ( 2 ) ≈ ≈ 1,443 {\\displaystyle c\\geq \\ln ^{-1}(2)\\approx 1{,}443} I.V.: T ( n ) ≤ ≤ c ⋅ ⋅ n ln ⁡ ⁡ ( n ) {\\displaystyle T(n)\\leq c\\cdot n\\ln(n)} für n ≥ ≥ n 0 {\\displaystyle n\\geq n_{0}} I.S.: n → n + 1: Da man für ein n0 gezeigt hat, dass T(n) ≤ c⋅n⋅ln(n) korrekt ist, stimmt die Vermutung. (Es zeigt sich, dass eine Konstante c ≥ 1,443 ausreicht.)

Damit folgt für T(n): T ( n ) ∈ ∈ O ( n ln ⁡ ⁡ ( n ) ) {\\displaystyle T(n)\\in O(n\\ln(n))}

• `!Beispiel (2)`!: T ( n ) = 8 T ( n 2 ) + n 3 ln ⁡ ⁡ ( n ) {\\displaystyle T(n)=8T\\left({\\frac {n}{2}}\\right)+n^{3}\\ln(n)}

Siehe zu demselben Beispiel auch die Aufwandsabschätzung mit dem `F33f`_`[Θ-Kalkül`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Landau-Symbole]`_`f im Artikel zum `F33f`_`[Mastertheorem`:/page/entry.mu`zim=wikipedia_de_all_nopic_2026-01.zim|entry_path=Master-Theorem]`_`f.

1. Vermutung: T ( n ) ∈ ∈ O ( n 3 ln 2 ⁡ ⁡ ( n ) ) ⟹ ⟹ T ( n ) ≤ ≤ c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( n ) {\\displaystyle T(n)\\in O\\left(n^{3}\\ln ^{2}(n)\\right)\\Longrightarrow T(n)\\leq c\\cdot n^{3}\\ln ^{2}(n)}

2. Annahme: T s u b ( n 2 ) = c ⋅ ⋅ ( n 2 ) 3 ln 2 ⁡ ⁡ ( n 2 ) − − t ( n ) {\\displaystyle T_{sub}\\left({\\frac {n}{2}}\\right)=c\\cdot \\left({\\frac {n}{2}}\\right)^{3}\\ln ^{2}\\left({\\frac {n}{2}}\\right)-t(n)} mit t ( n ) = b ⋅ ⋅ ln 2 ⁡ ⁡ ( 2 ) ( n 2 ) 3 {\\displaystyle t(n)=b\\cdot \\ln ^{2}(2)\\left({\\frac {n}{2}}\\right)^{3}} und b > 0 {\\displaystyle b>0}

3. Substitution: T ( n ) ≤ ≤ 8 T s u b ( n 2 ) + n 3 ln ⁡ ⁡ ( n ) {\\displaystyle T(n)\\leq 8T_{sub}\\left({\\frac {n}{2}}\\right)+n^{3}\\ln(n)}

4. Umformen: = 8 ( c ⋅ ⋅ ( n 2 ) 3 ln 2 ⁡ ⁡ ( n 2 ) − − b ⋅ ⋅ ln 2 ⁡ ⁡ ( 2 ) ( n 2 ) 3 ) + n 3 ln ⁡ ⁡ ( n ) {\\displaystyle =8\\left(c\\cdot \\left({\\frac {n}{2}}\\right)^{3}\\ln ^{2}\\left({\\frac {n}{2}}\\right)-b\\cdot \\ln ^{2}(2)\\left({\\frac {n}{2}}\\right)^{3}\\right)+n^{3}\\ln(n)} = c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( n 2 ) − − b ⋅ ⋅ ln 2 ⁡ ⁡ ( 2 ) n 3 + n 3 ln ⁡ ⁡ ( n ) {\\displaystyle =c\\cdot n^{3}\\ln ^{2}\\left({\\frac {n}{2}}\\right)-b\\cdot \\ln ^{2}(2)n^{3}+n^{3}\\ln(n)} = c ⋅ ⋅ n 3 ( ln ⁡ ⁡ ( n ) − − ln ⁡ ⁡ ( 2 ) ) ⋅ ⋅ ( ln ⁡ ⁡ ( n ) − − ln ⁡ ⁡ ( 2 ) ) − − b ⋅ ⋅ ln 2 ⁡ ⁡ ( 2 ) n 3 + n 3 ln ⁡ ⁡ ( n ) {\\displaystyle =c\\cdot n^{3}\\left(\\ln(n)-\\ln(2)\\right)\\cdot \\left(\\ln(n)-\\ln(2)\\right)-b\\cdot \\ln ^{2}(2)n^{3}+n^{3}\\ln(n)} = c ⋅ ⋅ n 3 ( ln 2 ⁡ ⁡ ( n ) − − 2 ln ⁡ ⁡ ( 2 ) ln ⁡ ⁡ ( n ) + ln 2 ⁡ ⁡ ( 2 ) ) − − b ⋅ ⋅ ln 2 ⁡ ⁡ ( 2 ) n 3 + n 3 ln ⁡ ⁡ ( n ) {\\displaystyle =c\\cdot n^{3}\\left(\\ln ^{2}(n)-2\\ln(2)\\ln(n)+\\ln ^{2}(2)\\right)-b\\cdot \\ln ^{2}(2)n^{3}+n^{3}\\ln(n)} = c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( n ) − − c ⋅ ⋅ n 3 2 ln ⁡ ⁡ ( 2 ) ln ⁡ ⁡ ( n ) + c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( 2 ) − − b ⋅ ⋅ ln 2 ⁡ ⁡ ( 2 ) n 3 + n 3 ln ⁡ ⁡ ( n ) {\\displaystyle =c\\cdot n^{3}\\ln ^{2}(n)-c\\cdot n^{3}2\\ln(2)\\ln(n)+c\\cdot n^{3}\\ln ^{2}(2)-b\\cdot \\ln ^{2}(2)n^{3}+n^{3}\\ln(n)} = c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( n ) − − c ⋅ ⋅ n 3 2 ln ⁡ ⁡ ( 2 ) ln ⁡ ⁡ ( n ) + n 3 ln ⁡ ⁡ ( n ) − − b ⋅ ⋅ ln 2 ⁡ ⁡ ( 2 ) n 3 + c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( 2 ) {\\displaystyle =c\\cdot n^{3}\\ln ^{2}(n)-c\\cdot n^{3}2\\ln(2)\\ln(n)+n^{3}\\ln(n)-b\\cdot \\ln ^{2}(2)n^{3}+c\\cdot n^{3}\\ln ^{2}(2)} = c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( n ) + n 3 ln ⁡ ⁡ ( n ) ⋅ ⋅ ( 1 − − c ⋅ ⋅ 2 ln ⁡ ⁡ ( 2 ) ) ⏟ ⏟ c ≥ ≥ 1 2 ln ⁡ ⁡ ( 2 ) + n 3 ln 2 ⁡ ⁡ ( 2 ) ⋅ ⋅ ( c − − b ) ⏟ ⏟ b ≥ ≥ c {\\displaystyle =c\\cdot n^{3}\\ln ^{2}(n)+{\\begin{matrix}\\underbrace {n^{3}\\ln(n)\\cdot (1-c\\cdot 2\\ln(2))} \\\\{}^{\\rm {c\\geq {\\frac {1}{2\\ln(2)}}}}\\\\[-4.5ex]\\end{matrix}}+{\\begin{matrix}\\underbrace {n^{3}\\ln ^{2}(2)\\cdot (c-b)} \\\\{}^{\\rm {\\ b\\geq c}}\\\\[-4.5ex]\\end{matrix}}}

≤ ≤ c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( n ) {\\displaystyle \\leq c\\cdot n^{3}\\ln ^{2}(n)} mit b ≥ ≥ c ≥ ≥ 2 ln − − 1 ⁡ ⁡ ( 2 ) {\\displaystyle \\ b\\geq c\\geq 2\\ln ^{-1}(2)}

5. Induktion: I.A.: n = 2 : T ( 2 ) ≈ ≈ 5 , 5 ≤ ≤ c ⋅ ⋅ 2 3 ln 2 ⁡ ⁡ ( 2 ) {\\displaystyle n=2:\\quad T(2)\\approx 5{,}5\\leq c\\cdot 2^{3}\\ln ^{2}(2)} mit c ≥ ≥ 1 {\\displaystyle c\\geq 1} I.V.: T ( n ) ≤ ≤ c ⋅ ⋅ n 3 ln 2 ⁡ ⁡ ( n ) {\\displaystyle T(n)\\leq c\\cdot n^{3}\\ln ^{2}(n)} für n ≥ ≥ n 0 {\\displaystyle n\\geq n_{0}} I.S.: n → n + 1: Da man für ein n0 gezeigt hat, dass T(n) ≤ c⋅n3ln2(n) korrekt ist und c eine beliebig große Konstante sein darf, stimmt die Vermutung. (Eine Konstante c ≥ 4 ist hinreichend groß für alle n.)

Damit folgt für T(n): T ( n ) ∈ ∈ O ( n 3 ln 2 ⁡ ⁡ ( n ) ) {\\displaystyle T(n)\\in O(n^{3}\\ln ^{2}(n))}

`c`F0af`_`[↑ Back to top`#top]`_`f`a